﻿#include <iostream>

using namespace std;

static void swap(int* pArr, int index1, int index2)
{
    if (index1 == index2) return;

    pArr[index1] = pArr[index1] ^ pArr[index2];
    pArr[index2] = pArr[index1] ^ pArr[index2];
    pArr[index1] = pArr[index1] ^ pArr[index2];
}

/**
 * 一个数组中，指定一个数字number，把小于number的数字放到数组左侧；<br></br>
 * 把等于number的数字放到数组中间; 把大于number的数字放到数字右侧。
 * @param pArr
 * @param left
 * @param right
 * @return
 */
static int* partition(int* pArr, int left, int right)
{
    int index = left;
    int leftIndex = left;
    int rightIndex = right;
    int target = pArr[right];
    while (index <= rightIndex)
    {
        if (pArr[index] < target)
        {
            swap(pArr, leftIndex, index);
            ++index;
            ++leftIndex;
        }
        else if (pArr[index] == target)
        {
            ++index;
        }
        else
        {
            swap(pArr, rightIndex, index);
            --rightIndex;
        }
    }

    int* partitionArr = (int*)malloc(sizeof(int) * 2);
    partitionArr[0] = leftIndex - 1;
    partitionArr[1] = rightIndex;
    return partitionArr;
}

static void quickSort(int* pArr, int left, int right) 
{
    if (left >= right) return;

    int randIndex = left + (rand() % (right - left + 1));
    swap(pArr, randIndex, right);
    auto partitionArr = partition(pArr, left, right);
    quickSort(pArr, left, partitionArr[0]);
    quickSort(pArr, partitionArr[1], right);
    free(partitionArr);
}

/**
 * 快速排序
 * 参考 荷兰国旗问题：
 * 一个数组中，指定一个数字number，把小于number的数字放到数组左侧；
 * 把等于number的数字放到数组中间；把大于number的数字放到数字右侧。
 */
int main_QuickSort()
{
    ios::sync_with_stdio(false);

    int arr[] = { 3, 7, 8, 46, 0, 2, 50, 3, 4, 12, 99, 10, 9 };
    int size = sizeof(arr) / sizeof(int);
    quickSort(arr, 0, size - 1);

    for (int i = 0; i < size; i++)
    {
        printf("arr[%d]=%d\n", i, arr[i]);
    }

    return 0;
}
